// https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/

class Solution {
public:
    int maxDistance(vector<int>& p, int m) {
        sort(p.begin(), p.end());

        auto check = [&](int mid) {
            int cnt = 0, pre = p[0];
            for (int i = 1; i < p.size(); i++) {
                if (p[i] - pre >= mid) {
                    cnt++;
                    pre = p[i];
                }
            }
            return cnt >= m - 1;
        };

        int l = 0, r = p.back() - p[0] + 1;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (check(mid)) l = mid;
            else r = mid;
        }
        return l;
    }
};